package com.arron.algorithm.leetcodetop100.二叉树;


import com.arron.algorithm.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 116. 填充每个节点的下一个右侧节点指针
 */
public class ConnectNode {



    //使用递归的方式实现
    public Node connect(Node root) {
        if (root == null){
            return  root;
        }

        connectBy(root.left,root.right);

        return root;

    }


    public void  connectBy(Node node1,Node node2){

        if (node1 == null || node2 == null){
            return;
        }
        node1.next = node2;
        //同一个父节点
        connectBy(node1.left,node1.right);
        connectBy(node2.left,node2.right);
        //不同父节点
        connectBy(node1.right,node2.left);

    }




    //使用层次遍历二叉树的方式连接
    public Node connect01(Node root) {

        if(root==null) {
            return root;
        }

        LinkedList<Node> queue = new LinkedList<>();

        queue.offer(root);


        while (!queue.isEmpty()){
            int size = queue.size();
            //将队列的元素串起来
            Node temp = queue.get(0);

            for (int i = 1; i < size; i++) {
                temp.next = queue.get(i);
                temp = queue.get(i);
            }

            //将元素放入队列中
            for (int i = 0; i < size; i++) {
                Node poll = queue.poll();

                if (poll.left!=null){

                    queue.offer(poll.left);

                }
                if (poll.right!=null){
                    queue.offer(poll.right);
                }

            }

        }
        return root;
    }




}
